class Solution {//m*n
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& height) {
        int rows = height.size();
        int cols = height[0].size();
        vector<vector<char>> pacific(rows, vector<char>(cols, 0));
        vector<vector<char>> atlantic(rows, vector<char>(cols, 0));

        int directions[4][2] = {
            {1, 0}, {-1, 0}, {0, 1}, {0, -1}
        };

        auto dfs = [&](auto&& dfs, int row, int col,
                       vector<vector<char>>& visited) -> void {

            visited[row][col] = 1;

            for (auto& direction : directions) {
                int nextRow = row + direction[0];
                int nextCol = col + direction[1];

                if (nextRow < 0 || nextRow >= rows ||
                    nextCol < 0 || nextCol >= cols)
                    continue;

                if (visited[nextRow][nextCol])
                    continue;

                if (height[nextRow][nextCol] < height[row][col])
                    continue;

                dfs(dfs, nextRow, nextCol, visited);
            }
        };

        for (int col = 0; col < cols; ++col) {
            dfs(dfs, 0, col, pacific);              // 上
            dfs(dfs, rows - 1, col, atlantic);      // 下
        }

        for (int row = 0; row < rows; ++row) {
            dfs(dfs, row, 0, pacific);              // 左
            dfs(dfs, row, cols - 1, atlantic);      // 右
        }

        vector<vector<int>> answer;

        for (int row = 0; row < rows; ++row)
            for (int col = 0; col < cols; ++col)
                if (pacific[row][col] && atlantic[row][col])
                    answer.push_back({row, col});

        return answer;
    }
};